perm filename CMPARE[00,BGB] blob
sn#115065 filedate 1974-08-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00006 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {⊂C<NαCOMPARING.λ30P80I425,0JCFA} SECTION 8.
C00007 00003 ⊂8.1 A Polygon Matching Method.⊃
C00013 00004 ⊂8.2 Geometric Normalization of Polygons.⊃
C00017 00005 ⊂8.3 Compare by Recursive Windowing.⊃
C00019 00006 ⊂8.4 Related Work and Work Yet To Be Done.⊃
C00021 ENDMK
C⊗;
{⊂C;<N;αCOMPARING.;λ30;P80;I425,0;JCFA} SECTION 8.
{JCFD} IMAGE COMPARING.
{λ10;W250;JAFA}
8.0 Introduction to Image Comparing.
8.1 A Polygon Matching Method.
8.2 Geometric Normalization of Polygons.
8.3 Compare by Recursive Windowing.
8.4 Related Work and Work Yet To Be Done.
{λ30;W0;I950,0;JU;FA}
⊂8.0 Introduction to Image Comparing.⊃
The image compare process is both the <"keystone of the
arch"> as well as the <"weakest link of the chain">. By comparing
images, the 3-D modeling and the 2-D image processing are finally
linked, however as will be apparent the implementation to date
demonstates only a small part of what is
possible. In the feedback perception design, there are three classes
of compare operations: verification, revelation and recognition
which may be applied to each of the three kinds of image data
structures: raster, contour and mosaic. The verify compare finds the
corresponding entities between a predicted image and a perceived
image for the sake of calibration measurement and for the sake of
eliminating already know features from further consideration.
In vision for inductrial machine assembly, calibration measurements suddenly seem
to be the only kind of vision necessary in many factory situations.
The reveal compare involves finding the corresponding entities in two
percieved images, so that the location and extent of new objects can
be solved. Finally, the recognition compare involves matching a
percieved entity with one of a set of prototype entities.
From the view point of modeling the lowest level compare
operation should somehow be arranged to be a one to one template
match rather than a multi dimensional statistical discrimination or a
graph isomorphism test. That is if the entities to be matched are
incommensurate, the model designer censures
the model that generated an unrealistic
prediction rather than the pattern matcher which can not see a vague
resemblance. Clearly this position should not be taken to an extreme
and the present system could be enhanced by the inclusion of an
appropriate collection of traditional pattern matching techniques.
However, two techniques of commensuration that are naturally the
responsibility of a model builder are geometric normalization and
topological segmentation. Geometric normalization involves
eliminating the irrelevant differences such as location, orientation
and scale. Topological segmentation involves subdividing a complex
object into pieces, (perhaps even canonical pieces) so that only
simple small parts need be matched (that is the compare becomes
recursive). The remainder of this chapter explains a method for
matching structured images consisting of polygons. The most original
part of the method involves finding the correspondence, illustrated
in figure 8.1, for polygonal figures that fission or fuse from one
image to the next.
FIGURE 8.1 EXAMPLE OF POLYGON FUSION COMPARE.
⊂8.1 A Polygon Matching Method.⊃
The image compare process in CRE, connects the polygons and
arcs of one image with corresponding polygons and arcs of another
image. CRE's compare solves the problem of correlating polygons
between two similar images and is composed of four steps:
{λ10;JA}
1. Compute polygonal lamina inertia tensors, <lamten nodes>.
2. Compare and connect polygons one to one at corresponding levels of the nested polygon tree.
3. Compare and connect polygons two to one at corresponding levels of the nested polygon tree.
4. Compare and connect vertices of connected polygons using recursive windowing.
{λ30;JU}
First, the lamina inertia tensor nodes (called <lamten>'s) of
all the polygons of an image are computed. A lamten node contains
the center of mass as well as the tensor of a polygon. The meaning
of the inertia tensor is that it characterizes each polygon as a
rectangle of a certain length and width at a particular location and
oriention; and of further importance such inertia tensors can be
added to characterize two or more polygons by a single rectangle. It
is the lamten rectangles that provide a basis for normalization.
Second, all the lamtens of the polygons of one level of the
first image are compared with all the lamtens of the polygons of the
corresponding level of the second image for nearly exact match. The
potentially (M*N/2) compares is avoided by sorting on the center of
mass locations. In CRE, which is intended for comparing sequences
of pictures of natural scenes; match for center of mass location is
tested first and most strictly, followed by match for inertia.
Pointers between matching polygons are placed in two link positions
of the polygon nodes and the polygons are considered to be matched.
Third, all the unmated polygons of a level are considered
two at a time and a fusion lamten node for each pair is made. The
potentially (N*N/2-N) fusion lamtens are avoided because there is a
maximum possible unmated inertia in the other image; if there are no
unmated polygons in one image then the extra polygons of the first
image can be ignored. In the event where there are unmated polygons
in corresponding levels of the two images, the multi-polygon fusion
lamten of one are compared with the single polygon lamten of the
other. The fusion (fission) compare solves the rather nasty problem,
of linking two contour polygons of one image with a single contour
polygon in the next image.
Fourth, the vertices of mated polygons are in turn compared
and mated. To start a vertex compare, the vertices of one polygon
are translated, rotated and dilated to get that polygon's lamten
rectangle coincidant with its mate (or mates). Conceptually, each
vertex of one polygon is compared with each vertex of the other
polygon(s) and the mutually closest vertices (closer than an epsilon)
are considered to be mated. Actually the potential (N*M) compares are
avoided by a recursive windowing scheme similar to that used in
hidden line elimination algorithms.
The results of vertex compare and mate are illustrated in
figure 8.2; the compare execution takes less than a second on images
such as the pump, blocks, and dolls that appear in the figure.
FIGURE 8.2 VERTEX MATING - PUMP, BLOCKS and DOLL.
⊂8.2 Geometric Normalization of Polygons.⊃
The lamina inertia tensor of a polygon with N sides is
computed by summation over N trapezoids. The trapezoid corresponding
to each side is formed by dropping perpendiculars <up> to the top of
the image frame; each such trapezoid consists of a rectangle an a
right triangle; since the sides of polygons are directed vectors the
areas of the triangles and rectangles can be arranged to take
positive and negative values such that a summation will describe the
interior region of the polygon as positive. The equations necessary
for computing the lamina inertia tensor of a polygon were derived
from material in Goldstein's Classical Mechanics, [Goldstein].
FIGURE 8.3 LAMTEN TRAPEZOID DECOMPOSITION.
{λ10;JA}
RECTANGLE'S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
MXX ← B*B*AREA/12; (B HEIGHT IN ROWS).
MYY ← A*A*AREA/12; (A WIDTH IN COLUMNS).
MZZ ← MXX + MYY;
PXY ← 0;
ORIENTED RIGHT TRIANGLE'S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS.
MXX ← B*B*AREA/18; (B HEIGHT IN ROWS).
MYY ← A*A*AREA/18; (A WIDTH IN COLUMNS).
MZZ ← MXX + MYY;
PXY ← -A*B*AREA/36;
SUMMATION OF LAMINA INERTIA TENSORS.
AREA ← (AREA1 + AREA2);
XCM ← (AREA1 * XCM1 + AREA2 * XCM2) / AREA;
YCM ← (AREA1 * YCM1 + AREA2 * YCM2) / AREA;
MXX ← MXX1 + YCM1*YCM1*AREA1 +
MXX2 + YCM2*YCM2*AREA2 - YCM*YCM*AREA;
MYY ← MYY1 + XCM1*XCM1*AREA1 +
MYY2 + XCM2*XCM2*AREA2 - XCM*XCM*AREA;
PXY ← PXY1 - XCM1*YCM1*AREA1 +
PXY2 - XCM2*YCM2*AREA2 + XCM*YCM*AREA;
ANGLE OF PRINCIPLE AXIS
The angle of the principle axis, PHI, lies in the interval -π/2 to π/2.
PHI ← 0.5*ATAN(2*PXY/(MYY-MXX))
PXY ← 0.5*(MYY - MXX)*TAN(2*PHI)
TRANSLATION OF LAMINA INERTIA TENSOR AWAY FROM CENTER OF MASS.
MXX' ← MXX + AREA*DY*DY;
MYY' ← MYY + AREA*DX*DX;
PXY' ← PXY - AREA*DX*DY;
ROTATION OF LAMINA INERTIA TENSOR ABOUT CENTER OF MASS.
C ← COSINE(PHI);
S ← SINE(PHI);
MXX' ← C*C*MXX + S*S*MYY - 2*C*S*PXY;
MYY' ← C*C*MYY + S*S*MXX + 2*C*S*PXY;
PXY' ← (C*C - S*S)*PXY + C*S*(MYY - MXX);
{λ30;JU}
⊂8.3 Compare by Recursive Windowing.⊃
The final step in the CRE polygon match (subsection 8.1) is
to link the corresponding vertices between two geometrically
normalized polygons (or sets of polygons) using a nearest neighbor
criterion. The nearest neighbors are found by recursive windowing,
intially all the vertices are pushed into one large window which is
subseqently split until there were few enough vertices contained in
the window to allow exhautive comparing. To make this windowing
technique applicable to the nearest neighbor problem a distance
criterion, <delta>, has to be declared so that the windows overlap by
that amount. Consequently the windows are no longer disjoint
rectangles, but are rather boxes with rounded corners, the smallest
possible window being a circle with radius, <delta>. The recursive
windowing technique is essentially a two dimensional partition sort,
the technique can be generalized for comparing edges and other
entities in 2-D or higher dimensions.
⊂8.4 Related Work and Work Yet To Be Done.⊃
To complete the visual feedback system, there remains yet to
be written an image compare that uses both raster based and polygon based
techniques. The two kinds of compares are symbiotic in that the
polygon compare could aim the raster correlator alleviating the need
to do bulk correlation over wide areas, and the raster correlator
could verify and improve the measurement of corresponding vertex
loci. At Stanford, image comparison by raster correlation techniques
is begin worked on by [Quam], Hannah and Morevac. Another approach
to comparing polygons is to examine their curvature, the curvature of
a polygon can be expressed as a parametric function of arc length;
two such functions can be normalized and alligned and differenced
using statistical techniques [Zahn].